package com.leetcodehot.problems;

import java.util.Arrays;

public class problems611 {
    /**
     * 首先明确计算规则：从示例 1 可以知道，对于三元组 (2,3,4) 和 (4,3,2)，我们只统计了其中的 (2,3,4)，并没有把 (4,3,2) 也统计到答案中，所以题目意思是把这两个三元组当成是同一个三元组，我们不能重复统计。
     *
     * 既然有这样的规则，那么不妨规定三角形的三条边 a,b,c 满足：
     *
     * 1≤a≤b≤c
     * 这可以保证我们在统计合法三元组 (a,b,c) 的个数时，不会把 (c,b,a) 这样的三元组也统计进去。
     *
     * 由于三角形两边之和大于第三边，我们有
     *
     * a+b>c
     * a+c>b
     * b+c>a
     * 上式中的 a+c>b 是必然成立的，因为 a+c≥a+b>b（注意 a 至少是 1）。
     *
     * 同样的，b+c>a 也必然成立，因为 b+c≥a+a=2a>a（注意 a 至少是 1）。
     *
     * 所以只需要考虑第一个式子，那么问题变成，从 nums 中选三个数，满足 1≤a≤b≤c 且 a+b>c 的方案数。
     *
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int k = 2; k < nums.length; k++) {
            int c = nums[k];
            int i = 0; // a=nums[i]
            int j = k - 1; // b=nums[j]
            while (i < j) {
                if (nums[i] + nums[j] > c) {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] > c 同时意味着：
                    // nums[i+1]+nums[j] > c
                    // nums[i+2]+nums[j] > c
                    // ...
                    // nums[j-1]+nums[j] > c
                    // 从 i 到 j-1 一共 j-i 个
                    ans += j - i;
                    j--;
                } else {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] <= c 同时意味着
                    // nums[i]+nums[j-1] <= c
                    // ...
                    // nums[i]+nums[i+1] <= c
                    // 所以在后续的内层循环中，nums[i] 不可能作为三角形的边长，没有用了
                    i++;
                }
            }
        }
        return ans;
    }
}
